BZOJ3626【LNOI2014】LCA <离线+树链剖分>

Problem

【LNOI2014】LCA

Description

给出一个个节点的有根树（编号为到，根节点为）。一个点的深度定义为。设表示点的深度，表示与的最近公共祖先。
有次询问，每次询问给出，求。

Input

第一行个整数。
接下来行，分别表示点到点的父节点编号。
接下来行，每行个整数。

Output

输出行，每行表示一个询问的答案。每个答案对取模输出

Sample Input

Sample Output

1
2

8
5

HINT

共组数据，与的规模分别为,,,,。

Source

数据已加强saffah

标签：树链剖分

Solution

傻逼树链剖分，练手居然还了一发…

首先有一个这样的暴力：对于每个询问，将到根的路径打标记，枚举，每次累加当前节点最近的标记节点的深度。
然后发现可以反转一下：对于每个询问，枚举，每次将当前结点到根路径上的所有结点权值，统计到根路径上的总权值即可。（权值相当于深度累加）。
这道题没有强制在线，于是可以把所有的询问都离线下来，拆成两个前缀询问和分别计算。如果将所有前缀询问按右端点位置排序，不难发现可以依次操作，每次将一个新的结点到根路径上的所有结点权值，操作完统计右端点在此结点上的所有前缀询问的答案。
注意模完两个前缀答案相减后可能出现负数，需要先加上。

Code

#include <bits/stdc++.h>
#define MOD 201314
#define MAX_N 50000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <int> G[MAX_N+5];
struct node {int t, p, id; bool f;} opt[(MAX_N<<1)+5];
int n, m, ind, ans[MAX_N+5], tr[MAX_N<<2], tag[MAX_N<<2];
int dep[MAX_N+5], fa[MAX_N+5], sz[MAX_N+5], son[MAX_N+5], top[MAX_N+5], dfn[MAX_N+5];
bool cmp(const node &x, const node &y) {return x.t <= y.t;}
void DFS(int u) {
    sz[u] = 1;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i]; if (v == fa[u]) continue;
        dep[v] = dep[u]+1, fa[v] = u, DFS(v), sz[u] += sz[v];
        if (!son[u] || sz[son[u]] < sz[v]) son[u] = v;
    }
}
void DFS(int u, int tp) {
    top[u] = tp, dfn[u] = ++ind; if (son[u]) DFS(son[u], tp);
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (((v = G[u][i])^fa[u]) && (v^son[u])) DFS(v, v);
}
void update(int v) {tr[v] = tr[v<<1]+tr[v<<1|1];}
void downtag(int v, int s, int t) {
    if (!tag[v]) return;
    int x = tag[v]; tag[v] = 0;
    (tr[v<<1] += x*(mid-s+1)%MOD) %= MOD;
    (tr[v<<1|1] += x*(t-mid)%MOD) %= MOD;
    (tag[v<<1] += x) %= MOD, (tag[v<<1|1] += x) %= MOD;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        (tr[v] += x*(t-s+1)%MOD) %= MOD;
        (tag[v] += x) %= MOD; return;
    }
    downtag(v, s, t);
    if (l <= mid) modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
    update(v);
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return (tr[v]+MOD)%MOD;
    int ret = 0; downtag(v, s, t);
    if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= MOD;
    if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= MOD;
    return (ret%MOD+MOD)%MOD;
}
void change(int u) {
    for (; u; u = fa[top[u]])
        modify(1, 1, n, dfn[top[u]], dfn[u], 1);
}
int getsum(int u) {
    int ret = 0;
    for (; u; u = fa[top[u]])
        (ret += query(1, 1, n, dfn[top[u]], dfn[u])) %= MOD;
    return (ret += MOD) %= MOD;
}
int main() {
    read(n), read(m);
    for (int i = 2, x; i <= n; i++)
        read(x), G[x+1].push_back(i);
    for (int i = 1, l, r, p; i <= m; i++)
        read(l), read(r), read(p), 
        opt[i*2-1].p = opt[i*2].p = p+1, 
        opt[i*2-1].id = opt[i*2].id = i, 
        opt[i*2-1].t = l, opt[i*2].t = r+1, 
        opt[i*2-1].f = false, opt[i*2].f = true;
    sort(opt+1, opt+m*2+1, cmp), DFS(1), DFS(1, 1);
    for (int i = 1, j = 0; i <= m*2; i++) {
        while (j < opt[i].t) change(++j);
        if (opt[i].f) (ans[opt[i].id] += getsum(opt[i].p)) %= MOD;
        else (ans[opt[i].id] += MOD-getsum(opt[i].p)) %= MOD;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", (ans[i]%MOD+MOD)%MOD);
    return 0;
}